import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: syyyy
 * Date: 2025-08-19
 * Time: 11:17
 */
public class MyBinaryTree {
    public static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val){
            this.val=val;
        }
    }

    public TreeNode root;

    public void createBinaryTree(TreeNode root){
        TreeNode node1=new TreeNode(1);
        TreeNode node2=new TreeNode(2);
        TreeNode node3=new TreeNode(3);
        TreeNode node4=new TreeNode(4);
        TreeNode node5=new TreeNode(5);
        TreeNode node6=new TreeNode(6);
        TreeNode node7=new TreeNode(7);

        node4.left=node2;
        node4.right=node6;
        node2.left=node1;
        node2.right=node3;
        node6.left=node5;
        node6.right=node7;

        root=node4;

    }

    //1.方法一
    public void levelOrder(TreeNode root){
        if(root==null){
            return;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()){
            TreeNode cur=queue.poll();
            System.out.print(cur.val+" ");
            if(cur.left!=null){
                queue.offer(cur.left);
            }
            if(cur.right!=null){
                queue.offer(cur.right);
            }
        }
        System.out.println();
    }
    //2.方法二
    public List<List<Integer>> levelOrder2(TreeNode root){
        List<List<Integer>> ret=new ArrayList<>();
        if(root==null){

            return ret;
        }

        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer> list=new ArrayList<>();
            int size=queue.size();
            while(size!=0){
                TreeNode cur=queue.poll();
                list.add(cur.val);
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
                size--;
            }
            ret.add(list);
        }
        return ret;
    }

    public boolean isSymmetric(TreeNode root){
        if(root == null){
            return true;
        }
        boolean ret=isSymmetricChild(root.left,root.right);
        //为什么要这么做，1.如果比较对称性要最全面，那么起码要深度为3的数，root的左树的左树的值要等于右树的右树的值，以此类推。。
        //如果只有两层的话，就只需要比较root.left是不是等于root.right  2.root本身不需要判断是否对称
        return ret;
    }

    public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree){
        if(leftTree==null && rightTree==null){
            return true;
        }
        if(leftTree==null&&rightTree!=null||leftTree!=null&&rightTree==null){
            return false;
        }
        if(leftTree.val!=rightTree.val){
            return false;
        }

        return isSymmetricChild(leftTree.left,rightTree.right)
                &&isSymmetricChild(leftTree.right,rightTree.left);
    }

    public int getHeight(TreeNode root){
        if(root==null){
            return 0;
        }

        int leftHeight=getHeight(root.left);
        int rightHeight=getHeight(root.right);

        return Math.max(leftHeight,rightHeight)+1;
    }

    //1.方法一
    public boolean isBalanced(TreeNode root){
        //任意一个子树的左右只差都要小于等于1
        if(root==null){
            return true;
        }
        int leftHeight=getHeight(root.left);
        int rightHeight=getHeight(root.right);

        return Math.abs(leftHeight-rightHeight)<=1
                && isBalanced(root.left)
                && isBalanced(root.right);
    }
    //多从重复计算，时间复杂度太高

    //2.方法二
    public boolean isBalanced2(TreeNode root){
        if(root==null){
            return true;
        }
        if(getHeight2(root)>0){
            return true;
        }
        return false;
    }

    public int getHeight2(TreeNode root){
        //我在计算左子树和右子树高度之差时，就判断好他们之间的高度差是不是小于等于1的，
        //如果是小于等于1的就一直返回-1
        if(root==null){
            return 0;
        }
        int leftHeight=getHeight2(root.left);
        if(leftHeight<0){
            return -1;
        }

        int rightHeight=getHeight2(root.right);
        if(rightHeight<0){
            return -1;
        }

        if(Math.abs(leftHeight-rightHeight)<=1){
            return Math.max(leftHeight,rightHeight)+1;
        }else{
            return -1;
        }
    }

    public TreeNode prev=null;
    public void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        root.left=prev;
        if(root.left!=null) {//第一个节点的left等于null就可以了，后面都不需要
            prev.right = root;
        }
        prev=root;
        inOrder(root.right);
    }


    public TreeNode Convert(TreeNode root){
        if(root==null){
            return null;
        }
        inOrder(root);//最后root会到原本的根节点那里
        TreeNode head=root;
        while (head.left!=null){
            head=head.left;
        }
        return head;
    }

    public static int i=0;
    public static TreeNode StringIntoBinaryTree(String str){
        TreeNode root=null;
        if(str.charAt(i)!='#'){
            root=new TreeNode(str.charAt(i));
            i++;
            root.left=StringIntoBinaryTree(str);
            root.right=StringIntoBinaryTree(str);
        }else{
            i++;
        }
        return root;
    }

    //判断是不是完全二叉树
    public boolean isCompleteTree(TreeNode root){
        if(root==null){
            return true;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode cur=queue.poll();
            if(cur!=null){
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else {
                break;
            }
        }
        while(!queue.isEmpty()){
            if(queue.peek()!=null){
                return false;
            }
            queue.poll();
        }
        return true;
    }
}
